Leetcode 123. Best Time to Buy and Sell Stock III 题解

题目链接

Leetcode 123. Best Time to Buy and Sell Stock III

题目内容

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example1:

Input: [3,3,5,0,0,3,1,4]

Output: 6

Example2:

Input: [1,2,3,4,5]

Output: 4

Example3:

Input: [7,6,4,3,1] Output: 0

解题思路

因为我是通过搜索Dynamic Programing搜索到的这题目，所以我们这个题目先采取DP的思路进行完成，通过思考，我们能较快得到一个DP状态转移方程如下: DP[k][i] = MAX(DP[k][i-1], price[i] - price[j] + DP[k-1][i-1]) K = 0~i-1; (通过k次交易在第i天内的最大收益)， 通过这个状态转移方程，我们就可以很快完成我们的编程，这里需要注意的是，我们不可以每一次遍历都对每一个j进行遍历，这样就会导致超时，我们可以在每一次执行时记录我们的minVal，优化之后，我们程序的复杂度就是O(n) = O(kn)。

Detail提交情况如下

在提交完后，我在discuss里还发现一种挺好的解法: 通过维护buy1, sell1, buy1, sell2来实现

状态转移方程如下

buy1 = max(buy1,  -prices[i]);
sell1 = max(sell1, buy1 + prices[i]);
buy2 = max(buy2, sell1 - prices[i]);
sell2 = max(sell2, buy2 + prices[i]);

时间复杂度为O(n),不过实际提交事件也是4ms

题目代码

第一种方法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0)
            return 0;
        int dp[3][prices.size()];
        memset(dp, 0, sizeof(dp));
        for (int k = 1; k <= 2; k++) {
            int minVal = prices[0];
            for (int i = 1; i < prices.size(); i++) {
                minVal = min(minVal, prices[i] - dp[k-1][i-1]);
                dp[k][i] = max(dp[k][i-1], prices[i] - minVal);
            }
        }

        return dp[2][prices.size() - 1];
    }
};

第二种方法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sell1 = 0;
        int sell2 = 0;
        int buy1 = INT_MIN;
        int buy2 = INT_MIN;

        for (int i = 0; i < prices.size(); i++) {
            buy1 = max(buy1,  -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);

        }
        return sell2;
    }
};